
// 43.字符串相乘
class Solution {

    string each_product(int x , string& str)
    {
        int n = str.size() , flag = 0;
        string ret;
        for(int i = n - 1 ; i >= 0 ; i--)
        {
            int y = str[i] - '0';
            int z = x * y + flag;
            flag = z/10;    
            ret += to_string(z%10);
        }
        if(flag) ret += to_string(flag);
        return ret;
    }

    string two_sum(string& str1 , string& str2)
    {
        int n = str1.size() , m = str2.size();
        string ret;
        int flag = 0 , i;
        for(i = 0 ; i < n || i < m || flag; i++)
        {
            int sum = 0;
            if(i < n) sum += str1[i] - '0';
            if(i < m) sum += str2[i] - '0';
            sum += flag;
            flag = sum/10;
            ret += to_string(sum%10);
        }
        return ret;
    }


public:
    string multiply(string num1, string num2) {
        int n = num1.size() , m = num2.size();

        // 此题不能转化为数字进行处理,因为会越界
        string zero = "" , ret;
        for(int i = m - 1 ; i >= 0 ; i--)            // 将num2拆开
        {
            string each = each_product(num2[i] - '0' , num1);
            each = zero + each;
            // 将ret与each相加
            ret = two_sum(ret , each);
            zero += "0";
        }
        reverse(ret.begin() , ret.end());
        while(ret.size() > 1 && ret.front() == '0') ret.erase(ret.begin());
        return ret;
    }
};